1. Technical Field
The present invention relates in general to data processing and, in particular, to branch prediction within a data processing system. Still more particularly, the present invention relates to a processor and method of branch prediction that select one of a plurality of branch predictions in accordance with the type of underlying condition upon which a branch depends.
2. Description of the Related Art
A state-of-the-art superscalar processor can comprise, for example, an instruction cache for storing instructions, one or more execution units for executing sequential instructions, a branch unit for executing branch instructions, instruction sequencing logic for routing instructions to the various execution units, and registers for storing operands and result data.
Branch instructions executed by the branch unit of the superscalar processor can be classified as either conditional or unconditional branch instructions. Unconditional branch instructions are branch instructions that change the flow of program execution from a sequential execution path to a specified target execution path and which do not depend upon a condition supplied by the occurrence of an event. Thus, the branch in program flow specified by an unconditional branch instruction is always taken. In contrast, conditional branch instructions are branch instructions for which the indicated branch in program flow may be taken or may not taken depending upon a condition within the processor, for example, the state of a specified condition register bit or the value of a counter.
Conditional branch instructions can be further classified as either resolved or unresolved, based upon whether or not the condition upon which the branch depends is available when the conditional branch instruction is evaluated by the branch unit. Because the condition upon which a resolved conditional branch instruction depends is known prior to execution, resolved conditional branch instructions can typically be executed and instructions within the target execution path fetched with little or no delay in the execution of sequential instructions. Unresolved conditional branches, on the other hand, can create significant performance penalties if fetching of sequential instructions is delayed until the condition upon which the branch depends becomes available and the branch is resolved.
Therefore, in order to minimize execution stalls, some processors speculatively execute unresolved branch instructions by predicting whether or not the indicated branch will be taken. Utilizing the result of the prediction, the instruction sequencing logic is then able to speculatively fetch instructions within a target execution path prior to the resolution of the branch, thereby avoiding a stall in the execution pipeline in cases in which the branch is subsequently resolved as correctly predicted. Conventionally, prediction of unresolved conditional branch instructions has been accomplished utilizing static branch prediction, which predicts resolutions of branch instructions based upon criteria determined by a compiler prior to program execution, or dynamic branch prediction, which predicts resolutions of branch instructions by reference to branch history accumulated on a per-address basis within a branch history table. More recently, even more elaborate two-level branch prediction methodologies have been proposed that utilize a first level of branch history that specifies the resolutions of the last K branch instructions to index into a second level of branch prediction storage that associates a resolution prediction with each (or selected ones) of the 2K-1 possible branch history patterns.
While conventional static and dynamic branch prediction methodologies have reasonably high prediction accuracies for some performance benchmarks, the severity of the performance penalty incurred upon misprediction in state-of-the-art processors having deep pipelines and high dispatch rates makes it desirable to improve prediction accuracy.
In accordance with the present invention, a processor having improved branch prediction accuracy includes at least one execution unit that executes sequential instructions and branch processing circuitry that processes branch instructions. The branch processing circuitry includes a number of branch prediction circuits that are each capable of providing a branch prediction for a conditional branch instruction, a selector that selects a branch prediction of a branch prediction circuit based upon the type of condition upon which the conditional branch instruction depends, and branch resolution circuitry that corrects for branch misprediction multiple pipeline stages later. The branch processing circuitry further includes path address logic that determines a path address of the selected branch prediction. Thus, branch prediction accuracy can be improved by considering the type of condition upon which a conditional branch instruction depends, rather than just branch history.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.